package com.algorithms;

import java.util.ArrayList;
import java.util.List;

public class test2 extends Thread {
	public void run(){
		String s1 = "My car is missing";
		String s2 = "This is my real car";
		
		String longestStr = findLongestString(s1, s2);
		System.out.println(longestStr);
	}
	
	private String findLongestString(String s1, String s2){
		List<String> similarList = new ArrayList<String>();
		
		for (int i = 0; i < s1.length(); i++){
			for (int j = 0; j < s2.length(); j++){
				
				if (s1.charAt(i) == s2.charAt(j)){
					int stepS1 = i, stepS2 = j;
					String similarStr = "";
					
					while (stepS1 < s1.length() && stepS2 < s2.length() && 
							(s1.charAt(stepS1) == s2.charAt(stepS2))){
						similarStr += s1.charAt(stepS1);
						stepS1++;
						stepS2++;
					}
					
					similarList.add(similarStr);
				}
				
			}
		}
		
		int longestSize = 0;
		int longestIdx = -1;
		for (int i = 0; i < similarList.size(); i++){
			if (longestSize < similarList.get(i).length()){
				longestIdx = i;
				longestSize = similarList.get(i).length();
			}
		}
		
		String longestStr = similarList.get(longestIdx);
		
		return longestStr;
	}
	
	public static void main(String args[]){
		new test2().start();
	}
}
